package com.wwz.leetcode;

import org.junit.Test;

public class LeetCode29 {

    public int divide(int dividend, int divisor) {
        if (dividend == 0) {
            return 0;
        }
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }
        boolean negative;
        // 用异或来计算是否符号相异  如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。(同为0，异为1)
        negative = (dividend ^ divisor) < 0;
        long beichushu = Math.abs((long) dividend);
        long chushu = Math.abs((long) divisor);
        int result = 0;
        /**
         * 我们可以以100/3为例
         *  2^n是1，2，4，8...2^31这种数，当n为31时，这个数特别大，100/2^n是一个很小的数，肯定是小于3的，所以循环下来，
         *
         *  当n=5时，100/32=3, 刚好是大于等于3的，这时我们将100-32*3=4，也就是减去了32个3，接下来我们再处理4，同样手法可以再减去一个3
         *
         *  所以一共是减去了33个3，所以商就是33
         */
        for (int i = 31; i >= 0; i--) {
            //  相当除数 从2^n 开始除
            if ((beichushu >> i) >= chushu) {
                // 将结果加上2^n
                result += 1 << i;
                // 将被除数减去2^n*divisor
                beichushu -= chushu << i;
            }
        }
        // 符号相异取反
        return negative ? -result : result;
    }

    @Test
    public void test() {
        System.out.println(divide(10, 3));
    }
}
